package leetcode.year2021.month9;

import java.util.Deque;
import java.util.LinkedList;

public class _25_01DeleteLastNNode19 {
  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    Deque<ListNode> stack = new LinkedList<ListNode>();

    ListNode currNode = dummy;
    while (currNode != null) {
      stack.push(currNode);
      currNode = currNode.next;
    }

    for (int i = 0; i < n; i++) {
      stack.pop();
    }
    ListNode prev = stack.peek();
    prev.next = prev.next.next;

    return dummy.next;
  }
  /**
   * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
   *
   * 进阶：你能尝试使用一趟扫描实现吗？
   *
   * 输入：head = [1,2,3,4,5], n = 2
   * 输出：[1,2,3,5]
   * 示例 2：
   *
   * 输入：head = [1], n = 1
   * 输出：[]
   * 示例 3：
   *
   * 输入：head = [1,2], n = 1
   * 输出：[1]
   *
   */
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
